import java.security.cert.CRL;
import java.util.ArrayList;
import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-02
 * Time: 14:54
 */
public class GraphByNode {
    static class Node{
        public int src;
        public int dest;
        public int weight;
        public Node next;

        public Node(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public char[] nodeArray;
    public HashMap<Character, Integer> nodes;
    public ArrayList<Node> nodeList;
    public boolean isDirect;

    public GraphByNode(int num, boolean isDirect) {
        this.nodeArray=new char[num];
        this.isDirect=isDirect;
        this.nodeList=new ArrayList<>(num);
        // 需要提前往 list 中存储一些数据, 不然虽然开辟了空间, 但是 size 仍然为 0, 获取元素时会越界
        for (int i = 0; i < num; i++) {
            nodeList.add(null);
        }
        this.nodes=new HashMap<>();
    }

    public void initNodes(char[] arr){
        int length=arr.length;
        for (int i = 0; i < length; i++) {
            nodeArray[i]=arr[i];
            nodes.put(arr[i], i);
        }
    }

    /**
     * 添加边
     * @param srcV
     * @param destV
     * @param weight
     */
    public void addEdge(char srcV, char destV, int weight){
        int srcIndex=nodes.get(srcV);
        int destIndex=nodes.get(destV);
        addEdgeChild(srcIndex, destIndex, weight);
        if(!isDirect){
            // 如果是无向图, 需要对称插入
            addEdgeChild(destIndex, srcIndex, weight);
        }
    }


    public void addEdgeChild(int srcIndex, int destIndex, int weight){
        Node cur=nodeList.get(srcIndex);
        // 检查这条边是不是已经存储过
        while(cur!=null){
            // 说明这条边已经存储了
            if(cur.dest==destIndex){
                return ;
            }
            cur=cur.next;
        }
        Node node=new Node(srcIndex, destIndex, weight);
        node.next=nodeList.get(srcIndex);
        nodeList.set(srcIndex, node);
    }

    public void printGraph(){
        int length=nodeArray.length;
        for (int i = 0; i < length; i++) {
            System.out.print(nodeArray[i]+"-> ");
            Node cur=nodeList.get(i);
            while(cur!=null){
                System.out.print(nodeArray[cur.dest]+"->");
                cur=cur.next;
            }
            System.out.println();
        }
    }

    public int getDegree(char srcV){
        int srcIndex=nodes.get(srcV);
        Node cur=nodeList.get(srcIndex);
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        // 如果是有向图, 还需要计算入度
        int length=nodeArray.length;
        if(isDirect){
            for (int i = 0; i < length; i++) {
                if(i!=srcIndex){
                    Node node=nodeList.get(i);
                    while(node!=null){
                        if(node.dest==srcIndex){
                            count++;
                        }
                        node=node.next;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {

        GraphByNode graph = new GraphByNode(4,true);
        char[] array = {'A','B','C','D'};
        graph.initNodes(array);

        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);

        System.out.println("getDevOfV:: "+graph.getDegree('A'));
        graph.printGraph();
    }
}
